/*
https://leetcode.cn/problems/shortest-distance-after-road-addition-queries-i/description/
3243. 新增道路查询后的最短距离 I
*/

class Solution {
public:
int bfs(vector<vector<int>>& ans,int n)
{
    queue<int>q;
    vector<int>arr(n,INT_MAX);
    q.push(0);
    arr[0]=0;
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        for(int i : ans[k])
        {
            if(arr[i]==INT_MAX)
            {
                arr[i]=arr[k]+1;
                q.push(i);
            }
        }
    }
    return arr[n-1];
}

// void BFS(graph g,int v) {
//    初始化队列;
//    访问v;visited[v]=1;
//    v入队;
//    while(队不空) {
//       v出队;
//       找v的第一个邻接点w;
//       while(w存在) {
//          if(w未访问过) {
//             访问w;visited[w]=1;
//             w入队;
//          }
//          求v的下一个邻接点w;
//       }
//    }
// }


    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<int>arr;
        vector<vector<int>>ans(n);
        for(int i=0;i<n-1;i++)
            ans[i].push_back(i+1);

        for(int i=0;i<queries.size();i++)
        {
            int a=queries[i][0];
            int b=queries[i][1];
            ans[a].push_back(b);
            arr.push_back(bfs(ans,n));
        }
        return arr;
    }
};